import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int[] index=new int[nums.length];
        int[] ret=new int[nums.length];
        List<Integer> list=new ArrayList<>();


        for(int i=0;i<nums.length;i++) index[i]=i;

        mer(ret,index,nums,0,nums.length-1);
        for(int i=0;i<nums.length;i++){
            list.add(ret[i]);

        }

        return list;

    }


    public void mer(int[] ret1,int[] index,int[] nums,int l,int r){
        if(l>=r) return;
        int ret=0;
        int mid=(l+r)/2;
        mer(ret1,index,nums,l,mid);
        mer(ret1,index,nums,mid+1,r);
        int[] tmp=new int[r-l+1];
        int[] tmp1=new int[r-l+1];

        int cur1=l,cur2=mid+1,i=0;

        while(cur1<=mid&&cur2<=r){
            if(nums[cur1]<=nums[cur2]){
                tmp[i]=nums[cur2];
                tmp1[i++]=index[cur2++];

            }
            else{
                tmp[i]=nums[cur1];
                tmp1[i++]=index[cur1];
                ret+=r-cur2+1;
                ret1[index[cur1]]+=r-cur2+1;
                cur1++;
            }
        }

        while(cur1<=mid){
            tmp[i]=nums[cur1];
            tmp1[i++]=index[cur1++];
        }
        while(cur2<=r){
            tmp[i]=nums[cur2];
            tmp1[i++]=index[cur2++];
        }
        for(int j=0;j<(r-l+1);j++){
            nums[l+j]=tmp[j];
            index[l+j]=tmp1[j];
        }


    }
}